Masala #0064

Uchburchakli sonlar:

Kvadrat sonlar:

Beshburchakli sonlar:

Oltiburchakli sonlar:

Endi navbat K burchakli sonlar haqida ketadi:

• K burchakli fraktalning tomonlar soni K ta;
• K burchakli fraktalning dastlabki elementi 1 ta nuqtadan iborat;
• K burchakli fraktalning barcha elementi bitta uchga tayangan holda hosil bo’ladi;
• K burchakli fraktalning N-elementi o’zidan oldingi elementidan hosil bo’ladi va N-elementning yuqori qatlamida har bir tomonida N tadan nuqta joylashgan bo’ladi.
• K burchakli sonning N – elementi K burchakli fraktalning N – elementidagi nuqtalar soniga teng.

INPUT.TXT kirish faylining yagona satrida bo’sh joy bilan ajratilgan holda 2 ta butun son, $K (3 ≤ K ≤ 10^9)$ va $N (1 ≤ N ≤ 10^9)$ sonlari berilgan.

OUTPUT.TXT chiqish faylida yagona butun son, K burchakli sonning N – elementini $10^9 + 7$ ga bo’lgandagi qoldig’ini chop eting.